package com.atguigu.tree.ThreadedBinaryTree;

/**
 * @author shkstart
 * @create 2021-08-16 22:29
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);


//        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
//        threadedBinaryTree.postOrder();
        threadedBinaryTree.setRoot(root);
        HeroNode search = threadedBinaryTree.postOrderSearch(3);
        System.out.println(search);
//        threadedBinaryTree.threadedNodes();
        //测试，以10号节点测试
//        HeroNode leftNode = node5.getLeft();
//        System.out.println("10号节点的前驱节点="+leftNode);
//        HeroNode rightNode = node5.getRight();
//        System.out.println("10号节点的后驱节点="+rightNode);
//        threadedBinaryTree.threaadedlist();

    }
}

//创建二叉树
class ThreadedBinaryTree{
    private HeroNode root;
    //为了实现线索化，需要创建当前节点的前驱节点的指针
    //在递归进行线索化时，pre 总是保留前一个结点
    private HeroNode pre=null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //重载threadedNodes
    public void threadedNodes(){
        this.threadedNodes(root);
    }
    //遍历二叉树
    public void threaadedlist(){
        HeroNode node=root;
        //节点为空，那就退出循环
        while (node!=null){
            //不断向左寻找，直到左子树为1
            while (node.getLeftType()==0){
                node=node.getLeft();
            }
            //输出
            System.out.println(node);
            //不断向右查找，直到右子树为0
            while (node.getRightype()==1){
                node=node.getRight();
                System.out.println(node);
            }
            //不断向右遍历
            node=node.getRight();
        }
    }
    //线索化二叉树
    public void threadedNodes(HeroNode node){
        //如果该对象为空，那就退出
        if (node==null){
            return;
        }
        //中序
        //左递归
        threadedNodes(node.getLeft());
        //中间对象的左节点
        if (node.getLeft()==null){
            //设置左节点为前驱节点
            node.setLeft(pre);
            //修改左节点的状态
            node.setLeftType(1);
        }
        //中间对象的右节点
        //设置的方法：移动下一方，用前一方指向下一方
        if (pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightype(1);
        }
        //移动节点
        pre=node;
        //右递归
        threadedNodes(node.getRight());
    }
    //删除节点
    public void delNode(int no){
        //保证根节点不为空
        if (root!=null){
            //检查根节点是否是删除节点
            if (root.getNo()==no){
                //如果是，那就置空
                root=null;
            }else {
                //如果不是，那就循环
                root.delNode(no);
            }
        }else {
            System.out.println("空树，不能删除！");
        }
    }
    //前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //前序查找
    public HeroNode preOrderSearch(int no){
        if (root!=null){
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }

    //中序查找
    public HeroNode infixOrderSearch(int no){
        if (root!=null){
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }

    //前序查找
    public HeroNode postOrderSearch(int no){
        if (root!=null){
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}
//创建节点
class HeroNode{
    private int no;
    private String name;
    //左右节点默认为空
    private HeroNode left;
    private HeroNode right;
    //1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    //2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
    private int leftType;
    private int rightype;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightype() {
        return rightype;
    }

    public void setRightype(int rightype) {
        this.rightype = rightype;
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    //删除节点
    public void delNode(int no){
        //检查左节点
        if (this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        //检查右节点
        if (this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        //递归左节点
        if (this.left!=null){
            this.left.delNode(no);
        }
        //递归右节点
        if (this.right!=null){
            this.right.delNode(no);
        }
    }
    //前序遍历
    public void preOrder(){
        //输出父节点
        System.out.println(this);
        //递归向左遍历
        if (this.left!=null){
            this.left.preOrder();
        }
        //递归向右遍历
        if (this.right!=null){
            this.right.preOrder();
        }

    }
    //中序遍历
    public void infixOrder(){
        //递归向左遍历
        if (this.left!=null){
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右遍历
        if (this.right!=null){
            this.right.infixOrder();
        }

    }

    //后序遍历
    public void postOrder(){
        //递归向左遍历
        if (this.left!=null){
            this.left.postOrder();
        }
        //递归向右遍历
        if (this.right!=null) {
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);

    }
    //前序查找法
    public HeroNode preOrderSearch(int no){
        System.out.println("前序遍历查找");
        //比较当前节点是否是该查找的点
        if (this.no==no){
            return this;
        }
      HeroNode resNode=null;
        //如果不是，则向左递归
        if (this.left!=null){
            resNode = this.left.preOrderSearch(no);
        }
        //如果不是等于空，那就返回该查找的对象
        if (resNode!=null){
            return resNode;
        }
        //向左不行，那向右递归
        if (this.right!=null){
            resNode=this.right.preOrderSearch(no);
        }
        //无论行不行，哪怕为空也可以返回
        return resNode;
    }
    //中序查找法
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode=null;
        //向左递归
        if (this.left!=null){
            resNode=this.left.infixOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        //开始一一比对
        System.out.println("中序遍历查找");
        if (this.no==no){
            return this;
        }
        //向右递归
        if (this.right!=null){
            resNode=this.right.infixOrderSearch(no);
        }
        return resNode;

    }
    //后序查找法--唯一不同，需要两次比较
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;

        //向左递归
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //向右递归
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //开始一一比对
        System.out.println("后序遍历查找");
        if (this.no == no) {
            return this;
        }

        return resNode;
    }
}